﻿//2209. 用地毯覆盖后的最少白色砖块
//给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。
//floor[i] = '0' 表示地板上第 i 块砖块的颜色是 黑色 。
//floor[i] = '1' 表示地板上第 i 块砖块的颜色是 白色 。
//同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色 的地毯长度都为 carpetLen 块砖块。
//请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。
//请你返回没被覆盖的白色砖块的 最少 数目。


class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen)
    {
        //盖住最多的白色砖块
        //dp[i][j] 前i个砖块使用了j个地毯最少有多少未被覆盖的砖块
        //dp[i][j]=dp[i-1][j]+ 1?0 , dp[i-carpetLen][j-1] 
        //在i处放置地毯 在i处不放置地毯
        int n = floor.size();
        vector<vector<int>> dp(n + 1, vector<int>(numCarpets + 1, 0x3f3f3f3f));
        for (int i = 0; i < numCarpets; i++)
        {
            dp[0][i] = 0;
        }
        for (int i = 1; i <= n; i++)
        {
            dp[i][0] = dp[i - 1][0] + (floor[i - 1] == '1');
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= numCarpets; j++)
            {
                //不盖
                int x = dp[i - 1][j] + (floor[i - 1] == '1');
                //盖
                int y = dp[max(0, i - carpetLen)][j - 1];
                dp[i][j] = min(x, y);
            }
        }
        return dp[n][numCarpets];
    }
};